25. K 个一组翻转链表
25. K 个一组翻转链表
zhou25. K 个一组翻转链表
题目
给你链表的头节点 head
,每 k
个节点一组进行翻转,请你返回修改后的链表。
k
是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k
的整数倍,那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
思路
首先是k的不确定导致我们需要得知有多少个总的节点,才能实现题目的要求,所以先统计节点个数。
剩下的实现有两个关键点:第一个是如何翻转链表,第二个是哨兵节点
如何翻转链表
翻转的第一步得是翻转1,2,3,4之间的顺序
然后把4放到前面,把1放到后面,让1指向5
接下来我们详细进行实现
如果我们要改变一个节点的顺序,我们得把当前节点的next变成pre,所以我们一共要记录三个节点。
如果我们需要改变2的顺序(在此之前已经改变了1的顺序了)然后我们将cur->next = pre
接着把指针们都往后移
也就是
pre = cur
cur = nxt
nxt = nxt.next
后面往复便可以了,值得一提的是k个节点之后,我们需要将前后拼接起来
具体的操作:
在后半段,我们刚处理完,情况是这样的
最后我们要把1节点连接到8节点上,把5节点的next记为nullptr。我们先把1节点记为P0
那么。我们需要做这样的操作:
P0->next->next = null
P0->next = pre
为了方便下一段k操作,我们还需要更新P0
P0 = P0->next
因为数据在更新,所以我们得调整一下顺序和形式,(注意每次P0->next
所代指的节点到底是哪个)总的代码是:
auto nxt = P0->next
P0->next->next = null
P0->next = pre
P0 = nxt
哨兵节点
在上面展示的过程中,我们是以5-8为举例的,但如果我们要处理的数据是1-4的话,我们会没有P0可用,所以我们需要一个哨兵节点来当P0,具体的实现是:
ListNode *dummy = new ListNode(0, head), *p0 = dummy;
使用一个新链表,添加一个节点0,指向head
处理完第一段k就让0节点的next指向4,更新P0,让P0指针指向下一段k的P0的位置
就可以了
代码
1 | class Solution { |
结束
适用一切翻转链表的题目,好题,记录记录